/*
桶排序（Bucket Sort）也是一种非比较排序算法，它的基本思想是将待排序的一组数据分到有限数量的桶中，然后在每个桶中再进行排序。
它的时间复杂度为 $O(n+k)$，其中 $k$ 表示桶的个数。桶排序要求输入的数据必须满足一定的分布规律，也就是不能太分散，否则桶的数量将过大，而造成空间的浪费
感觉是希尔排序和计数排序的混合
 */
function bucketSort(arr, bucketSize = 5) {
    if (arr.length <= 1) {
        return arr;
    }
    // 找到最大值和最小值
    let max = arr[0];
    let min = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    // 计算桶的数量
    const bucketCount = Math.floor((max - min) / bucketSize) + 1;
    const buckets = Array.from({ length: bucketCount }, () => []);
    // 将数据分到不同桶中
    for (let i = 0; i < arr.length; i++) {
        const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
        // 设最小值为0 桶size为5 分成多个桶的示例为：[0,2,3],[5,7,9],[11,14]
        buckets[bucketIndex].push(arr[i]);
    }
    // 对每个桶中的数据进行排序
    let startIndex = 0;
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i].length > 0) {
            // 桶内元素进行插入排序
            insertionSort(buckets[i]);
            // 对桶内元素排完后 更新原数组的排序
            for (let j = 0; j < buckets[i].length; j++) {
                arr[startIndex + j] = buckets[i][j];
            }
            startIndex += buckets[i].length;
        }
    }
    return arr;
}
// 插入排序
function insertionSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    for (let i = 1; i < arr.length; i++) {
        let temp = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    return arr;
}
